---
title: "Mzc和男家丁的游戏"
created: 2025-11-28
tags:
  - 算法
---

# Mzc和男家丁的游戏

## 题目 [Mzc和男家丁的游戏](https://luogu.com.cn/problem/P2298)

mzc 家很有钱（开玩笑），他家有 n 个男家丁（做过上一弹的都知道）。他把她们召集在了一起，他们决定玩捉迷藏。现在 mzc 要来寻找他的男家丁，大家一起来帮忙啊！

由于男家丁数目不多，再加上 mzc 大大的找人水平很好，所以一次只需要找一个男家丁。

输入格式

第一行有两个数 n,m，表示有 $n$ 行 m 列供男家丁躲藏，

之后 n 行 m 列的矩阵，`m` 表示 mzc，`d` 表示男家丁，`#` 表示不能走，`.` 表示空地。

输出格式

一行，若有解：一个数 sum，表示找到男家丁的最短移动次数。

若无解：输出 `No Way!`。

样例 #1

样例输入 #1

```text
5 6
.#..#.
....#.
d.....
#####.
m.....
```

样例输出 #1

```text
12
```

提示

$3 \leq m,n \leq 2000$。

由于 mzc 大大十分着急，所以他只能等待 1s。

## 思路分析

洛谷真的屎一样的网站 还以为哪个细节忽略了改半天

结果所有题解也过不了 都是runtime error

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=2010;

char g[N][N];

int d[N][N];

int n,m;

int startx,starty,targetx,targety;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		if(g[ux][uy]=='d'){

			return d[ux][uy];

		}

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && (g[nx][ny]=='.' || g[nx][ny]=='d')){

				q.push({nx,ny});

				d[nx][ny]=d[ux][uy]+1;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<n;i++)

		cin>>g[i];

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			if(g[i][j]=='m')

				startx=i,starty=j;

		}

	}

	int res=bfs(startx,starty);

	if(res==-1)

		cout<<"No Way!"<<endl;

	else

		cout<<res<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[Bronze Lilypad Pond B|Bronze Lilypad Pond B]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/BFS/迷宫问题（最短路）/奇怪的电梯|奇怪的电梯]]